#include <limits.h>
#include <stddef.h>
#include "mem.h"
#include "assert.h"
#include "arith.h"
#include "set.h"
#define T Set_T
struct T {
	int length;
	unsigned timestamp;
	int (*cmp)(const void *x, const void *y);
	unsigned (*hash)(const void *x);
	unsigned size;
	struct member {
		struct member *link;
		const void *member;
	} **buckets;
};
static int cmpatom(const void *x, const void *y) {
	return x != y;
}
static unsigned hashatom(const void *x) {
	return (unsigned long)x>>2;
}
static T copy(T t, int hint) {
	T set;
	assert(t);
	set = Set_new(hint, t->cmp, t->hash);
	{ unsigned i;
	  struct member *q;
	  for (i = 0; i < t->size; i++)
	  	for (q = t->buckets[i]; q; q = q->link)
		{
			struct member *p;
			const void *member = q->member;
			int i = (*set->hash)(member)%set->size;
			NEW(p);
			p->member = member;
			p->link = set->buckets[i];
			set->buckets[i] = p;
			set->length++;
		}
	}
	return set;
}
T Set_new(int hint, int cmp(const void *x, const void *y),
	unsigned hash(const void *x)) {
	T set;
	int i;
	static int primes[] = { 317, 317, 691, 1399, 2801,
		INT_MAX };
	assert(hint >= 0);
	for (i = 1; primes[i] < hint; i++)
		;
	set = CALLOC(1, sizeof *set +
			primes[i-1]*sizeof set->buckets[0]);
	set->size = primes[i-1];
	set->cmp  = cmp  ?  cmp : cmpatom;
	set->hash = hash ? hash : hashatom;
	set->buckets = (void *)(set + 1);
	return set;
}
int Set_member(T set, const void *member) {
	int i;
	struct member *p;
	assert(set);
	assert(member);
	i = (*set->hash)(member)%set->size;
	for (p = set->buckets[i]; p; p = p->link)
		if ((*set->cmp)(member, p->member) == 0)
			break;
	return p != NULL;
}
void Set_put(T set, const void *member) {
	int i;
	struct member *p;
	assert(set);
	assert(member);
	i = (*set->hash)(member)%set->size;
	for (p = set->buckets[i]; p; p = p->link)
		if ((*set->cmp)(member, p->member) == 0)
			break;
	if (p == NULL) {
		NEW(p);
		p->member = member;
		p->link = set->buckets[i];
		set->buckets[i] = p;
		set->length++;
	} else
		p->member = member;
	set->timestamp++;
}
void Set_remove(T set, const void *member) {
	int i;
	struct member **pp;
	assert(set);
	assert(member);
	set->timestamp++;
	i = (*set->hash)(member)%set->size;
	for (pp = &set->buckets[i]; *pp; pp = &(*pp)->link)
		if ((*set->cmp)(member, (*pp)->member) == 0) {
			struct member *p = *pp;
			*pp = p->link;
			FREE(&p);
			set->length--;
			break;
		}
}
int Set_length(T set) {
	assert(set);
	return set->length;
}
void Set_free(T *set) {
	assert(set && *set);
	if ((*set)->length > 0) {
		unsigned i;
		struct member *p, *q;
		for (i = 0; i < (*set)->size; i++)
			for (p = (*set)->buckets[i]; p; p = q) {
				q = p->link;
				FREE(&p);
			}
	}
	FREE(set);
}
void Set_map(T set, void apply(const void *member, void *cl),
	void *cl) {
	unsigned i, stamp;
	struct member *p;
	assert(set);
	assert(apply);
	stamp = set->timestamp;
	for (i = 0; i < set->size; i++)
		for (p = set->buckets[i]; p; p = p->link) {
			apply(p->member, cl);
			assert(set->timestamp == stamp);
		}
}
void **Set_toArray(T set, void *end) {
	unsigned i, j = 0;
	void **array;
	struct member *p;
	assert(set);
	array = ALLOC((set->length + 1)*sizeof *array);
	for (i = 0; i < set->size; i++)
		for (p = set->buckets[i]; p; p = p->link)
			array[j++] = (void *)p->member;
	array[j] = end;
	return array;
}
T Set_union(T s, T t) {
	assert( s ||  t);
	assert(!s || !t || s->cmp  == t->cmp);
	assert(!s || !t || s->hash == t->hash);
	if (s == NULL)
		return copy(t, t->size + 1);
	else if (t == NULL)
		return copy(s, s->size + 1);
	else {
		T set = copy(s, Arith_max(s->size, t->size) + 1);
		unsigned i;
		struct member *q;
		for (i = 0; i < t->size; i++)
			for (q = t->buckets[i]; q; q = q->link)
			{
				struct member *p;
				const void *member = q->member;
				int i = (*set->hash)(member)%set->size;
				NEW(p);
				p->member = member;
				p->link = set->buckets[i];
				set->buckets[i] = p;
				set->length++;
			}
		return set;
	}
}
T Set_inter(T s, T t) {
	assert( s ||  t);
	assert(!s || !t || s->cmp  == t->cmp);
	assert(!s || !t || s->hash == t->hash);
	if (s == NULL)
		return Set_new(t->size + 1, t->cmp, t->hash);
	else if (t == NULL)
		return Set_new(s->size + 1, s->cmp, s->hash);
	else if (s->length < t->length)
		return Set_inter(t, s);
	else {
		T set = Set_new(Arith_min(s->size, t->size) + 1,
			s->cmp, s->hash);
		unsigned i;
		struct member *q;
		for (i = 0; i < t->size; i++)
			for (q = t->buckets[i]; q; q = q->link)
			if (Set_member(s, q->member))
				{
					struct member *p;
					const void *member = q->member;
					int i = (*set->hash)(member)%set->size;
					NEW(p);
					p->member = member;
					p->link = set->buckets[i];
					set->buckets[i] = p;
					set->length++;
				}
		return set;
	}
}
T Set_minus(T t, T s) {
	assert( s ||  t);
	assert(!s || !t || s->cmp  == t->cmp);
	assert(!s || !t || s->hash == t->hash);
	if (t == NULL)
		return Set_new(s->size + 1, s->cmp, s->hash);
	else if (s == NULL)
		return copy(t, t->size + 1);
	else {
		T set = Set_new(Arith_min(s->size, t->size) + 1,
			s->cmp, s->hash);
		unsigned i;
		struct member *q;
		for (i = 0; i < t->size; i++)
			for (q = t->buckets[i]; q; q = q->link)
			if (!Set_member(s, q->member))
				{
					struct member *p;
					const void *member = q->member;
					int i = (*set->hash)(member)%set->size;
					NEW(p);
					p->member = member;
					p->link = set->buckets[i];
					set->buckets[i] = p;
					set->length++;
				}
		return set;
	}
}
T Set_diff(T s, T t) {
	assert( s ||  t);
	assert(!s || !t || s->cmp  == t->cmp);
	assert(!s || !t || s->hash == t->hash);
	if (s == NULL)
		return copy(t, t->size + 1);
	else if (t == NULL)
		return copy(s, s->size + 1);
	else {
		T set = Set_new(Arith_min(s->size, t->size) + 1,
			s->cmp, s->hash);
		unsigned i;
		struct member *q;
		for (i = 0; i < t->size; i++)
			for (q = t->buckets[i]; q; q = q->link)
			if (!Set_member(s, q->member))
				{
					struct member *p;
					const void *member = q->member;
					int i = (*set->hash)(member)%set->size;
					NEW(p);
					p->member = member;
					p->link = set->buckets[i];
					set->buckets[i] = p;
					set->length++;
				}
		{ T u = t; t = s; s = u; }
		{ unsigned i;
		  struct member *q;
		  for (i = 0; i < t->size; i++)
		  	for (q = t->buckets[i]; q; q = q->link)
			if (!Set_member(s, q->member))
				{
					struct member *p;
					const void *member = q->member;
					int i = (*set->hash)(member)%set->size;
					NEW(p);
					p->member = member;
					p->link = set->buckets[i];
					set->buckets[i] = p;
					set->length++;
				}
		}
		return set;
	}
}
static char rcsid[] = "$RCSfile: RCS/set.doc,v $ $Revision: 1.2 $";
